#ifndef HASTTABLE__H__
#define HASTTABLE__H__
#include "..\engine\memorymanager.h"

#ifdef _DEBUG
#include "..\engine\error.h"
#endif

/**************************************
*HashTable
*Dynamic list object for object storage
 **************************************/
template <class T, class K>
class HashTable
{

public:
	struct Pair
	{
		T	*m_pData; 
		int m_Capacity; 
		int m_Count; 
		/*long unsigned int m_Key; */
		K m_Key; 
	}; 
	HashTable(void); 

	virtual ~HashTable(void); 
	T* operator[] (unsigned int idx); 
	T* Data(K key); 
	T* DataAtIndex(unsigned int idx); 
	Pair* GetPair(unsigned int idx)
	{
#ifdef _DEBUG
	if(!m_pPairs || idx > m_Count - 1)
	{
		EE_LOGERROR("Hash table out of bound access or invalid data"); 
		return NULL; 
	}
#endif
		
		return &m_pPairs[idx]; 
	}
	void Add(K key, T ptr); 
	void Empty(void); 
	void ClearAllocatedSpace(void);
	void Remove(K key, T ptr); 
	void Remove(K key); 
	void GetDataInfo(unsigned int* pKeyCount,unsigned int* pElementCount); 
	unsigned int TableKeyCount(void) const; 
	unsigned int KeyElementCount(K key); 
	unsigned int IndexElementCount(unsigned int idx) const; 
	K KeyAtTableIndex(unsigned int idx) const; 
	unsigned int TableElementCount(void) const; 
private:
	static const unsigned int STEP_SIZE = 5; 


	unsigned int m_Count; 
	unsigned int m_Capacity; 
	Pair *m_pPairs; 

	void RemoveKeyElement(Pair* pPair, T ptr); 
	void AddKeyElement(Pair* pPair, T ptr); 
	void FindPair(Pair **pOut, unsigned int* pIndex, K key); 

}; 

/**************************************
*
 **************************************/
template<class T, class K>
HashTable<T,K>::HashTable(void)
{	
	m_Capacity = 0; 
	m_Count = 0; 
	m_pPairs = NULL; 
}

/**************************************
*
 **************************************/
template<class T, class K>
HashTable<T,K>::~HashTable(void)
{	
#ifdef _DEBUG
	if((m_pPairs && !m_Count) || (!m_pPairs && m_Count))
		EE_LOGERROR("Hashtable is inconsistant")
#endif

	if(m_pPairs)
	{
		for(unsigned int i = 0;  i < m_Count;  i++)
			EE_SAFEDELETEARRAY(m_pPairs[i].m_pData); 
	}
	EE_SAFEDELETEARRAY(m_pPairs); 
}

/**************************************
*
 **************************************/
template<class T, class K>
void HashTable<T,K>::GetDataInfo(unsigned int* pKeyCount,unsigned int* pElementCount)
{	
#ifdef _DEBUG
	if(!m_pPairs)
		EE_LOGERROR("Hashtable is inconsistant")
#endif
	
	if(pKeyCount)
		*pKeyCount = m_Count; 
	if(pElementCount)
		*pElementCount = (m_Count > 0) ? TableElementCount() : 0; 
}

template<class T, class K>
void HashTable<T,K>::FindPair(Pair **pOut, unsigned int* pIndex, K key)
{
	if(!m_pPairs)
	{
		*pOut = NULL; 
		return; 
	}

	if( m_pPairs[0].m_Key == key)
	{
		*pOut = &m_pPairs[0]; 
		return; 
	}

	int minIdx = 0; 
	int maxIdx = m_Count - 1; 
	int index = (1 + maxIdx + minIdx) / 2; 

	for(; ; )
	{
		Pair* pPair = &m_pPairs[index]; 
		
		if( pPair->m_Key == key )
		{
			if(pIndex)
				*pIndex = index; 
			*pOut = pPair; 
			return; 
		}
		else if( key < pPair->m_Key )
		{
			maxIdx = index; 
		}
		else
		{
			minIdx = index; 
		}

		int newIndex = (1 + maxIdx + minIdx) / 2; 
		
		if(newIndex == index)
		{
			*pOut = NULL; 
			return; 
		}
		else
			index = newIndex; 
	}

}

/**************************************
 *Appends an object into the hash table
 **************************************/
template<class T, class K>
void HashTable<T,K>::Add(K key, T ptr)
{
	if(!m_pPairs)
	{
		m_Capacity = STEP_SIZE; 
		m_pPairs = EE_NEW Pair [m_Capacity]; 
		m_Count = 1; 

		Pair* pNewPair = &m_pPairs[0]; 
		pNewPair->m_Key = key; 
		pNewPair->m_Capacity = STEP_SIZE; 
		pNewPair->m_Count = 1; 
		pNewPair->m_pData = EE_NEW T [STEP_SIZE]; 
		
		pNewPair->m_pData[0] = ptr; 
	}
	else
	{
		Pair* pPair = NULL; 
		FindPair(&pPair, NULL, key); 
		
		if(pPair)
		{
			AddKeyElement(pPair, ptr); 
		}
		else
		{
			if(m_Count + 1 > m_Capacity)
			{
				m_Capacity += STEP_SIZE; 
				Pair* pPairRealloc = EE_NEW Pair [m_Capacity]; 
			
				EE_ZEROMEMORY(pPairRealloc, sizeof(Pair) * m_Capacity); 
				memcpy(&pPairRealloc[0], &m_pPairs[0], sizeof(Pair) * m_Count); 

				EE_SAFEDELETEARRAY(m_pPairs); 
				m_pPairs = pPairRealloc; 
			}	

			//for(int min = 0,max = m_Count - 1; ; )
			//{
			//	int idx = (max + min) / 2; 
			//	int findKey = m_pPairs[idx].m_Key; 

			//	if (key == findKey || min == max)
			//	{
			//		index = idx; 
			//		break; 
			//	}
			//	else if (key < findKey)
			//		max = idx; 
			//	else
			//		min = idx; 
			//}

			//	((min + max) / 2)
			unsigned int index = 0; 
			for(index = 0;  index < m_Count && key > m_pPairs[index].m_Key;  index++)
			{}

			//if(index > 0)
			//	memcpy(&pPairRealloc[0], &m_pPairs[0], sizeof(Pair) * index); 
			const int iShiftElementCount = m_Count - index; 
			if(iShiftElementCount > 0)
			{
				const unsigned int uiShiftElementSize = sizeof(Pair) * iShiftElementCount; 
				Pair* pTemp = EE_NEW Pair [iShiftElementCount]; 
				memcpy(pTemp, &m_pPairs[index], uiShiftElementSize); 
				memcpy(&m_pPairs[index+1], pTemp, uiShiftElementSize ); 
				EE_SAFEDELETEARRAY(pTemp); 
				//memcpy(&pPairRealloc[index+1], &m_pPairs[index], sizeof(Pair) * (m_Capacity - index)); 
			}
			else
			{

			//END element
			}
			
			Pair* pModifyPair = &m_pPairs[index]; 
			pModifyPair->m_Capacity = 0; 
			pModifyPair->m_Count = 0; 
			pModifyPair->m_Key = key; 
			pModifyPair->m_pData = NULL; 
			AddKeyElement(&m_pPairs[index], ptr); 
			
			m_Count++; 
		}
	}
}

/**************************************
 *Clears all allocated space within the 
 *list
 **************************************/
template<class T, class K>
void HashTable<T,K>::ClearAllocatedSpace(void)
{
	for(unsigned int i = 0;  i < m_Count;  i++)
		EE_SAFEDELETEARRAY(m_pPairs[i].m_pData); 

	EE_ZEROMEMORY(m_pPairs, sizeof(Pair) * m_Count); 
	m_Count = 0; 
}

/**************************************
 *Removes all objects from the list
 **************************************/
template<class T, class K>
void HashTable<T,K>::Empty(void)
{
#ifdef _DEBUG
	if((m_pPairs && m_Count == 0) || (ISNULL(m_pPairs) && m_Count > 0))
	{
		EE_LOGERROR("Hash table is invalid"); 
		return; 
	}
#endif

	for(unsigned int i = 0;  i < m_Count;  i++)
		EE_SAFEDELETEARRAY(m_pPairs[i].m_pData); 

	EE_SAFEDELETEARRAY(m_pPairs); 
	m_Count = 0; 
}

template<class T, class K>
void HashTable<T,K>::AddKeyElement(Pair* pPair, T ptr)
{
#ifdef _DEBUG
	if(!pPair)
	{
		EE_LOGERROR("Hash table error"); 
		return; 
	}
#endif

	if(pPair->m_Count >= pPair->m_Capacity)
	{
		pPair->m_Capacity += STEP_SIZE; 

		T* pRealloc = EE_NEW T [pPair->m_Capacity]; 
		EE_ZEROMEMORY(pRealloc, sizeof(T) * pPair->m_Capacity); 
		
		memcpy(pRealloc, pPair->m_pData, sizeof(T) * pPair->m_Count); 

		EE_SAFEDELETEARRAY(pPair->m_pData); 
		pPair->m_pData = pRealloc; 
	}

	pPair->m_pData[pPair->m_Count] = ptr; 	
	pPair->m_Count ++; 
}

template<class T, class K>
void HashTable<T,K>::RemoveKeyElement(Pair* pPair, T ptr)
{
#ifdef _DEBUG
	if(!pPair)
	{
		EE_LOGERROR("Hash table error"); 
		return; 
	}
#endif

	for(int i = 0;  i < pPair->m_Count;  i++)
	{
		if(pPair->m_pData[i] == ptr)
		{
			if(i != pPair->m_Count - 1)
				pPair->m_pData[i] = pPair->m_pData[pPair->m_Count - 1]; 

			pPair->m_pData[pPair->m_Count - 1] = NULL; 
			pPair->m_Count--; 

			//Automatically flush
			if(pPair->m_Count < pPair->m_Capacity - STEP_SIZE)
			{
				T* pRealloc = EE_NEW T [ pPair->m_Count ]; 
				memcpy(pRealloc, pPair->m_pData, sizeof(T) * pPair->m_Count); 
		
				EE_SAFEDELETEARRAY(pPair->m_pData); 
				pPair->m_pData = pRealloc; 
				pPair->m_Capacity = pPair->m_Count; 
			}
		}
	}

	//If this was the last element in the key, remove the key
	if(pPair->m_Count == 0)
	{
		K key = pPair->m_Key; 
		Remove(key); 
	}
}

/**************************************
 *Removes an element from the list of
 *a key in the hashe table
 **************************************/
template<class T, class K>
void HashTable<T,K>::Remove(K key, T ptr)
{
	Pair* pPair = NULL; 
	FindPair(&pPair, NULL,key); 

	if(pPair)
	{
		if(pPair->m_Count == 0)
		{
			Remove(key); 
		}
		else
		{
			RemoveKeyElement(pPair,ptr); 
		}
	}
}

template<class T, class K>
void HashTable<T,K>::Remove(K key)
{
	Pair* pPair = NULL; 
	unsigned int keyIndex = 0; 
	FindPair(&pPair, &keyIndex, key); 

	if(pPair)
	{
		EE_SAFEDELETEARRAY(pPair->m_pData); 
#ifdef _DEBUG
		pPair->m_Capacity = 0; 
		pPair->m_Count = 0; 
		pPair->m_Key = 0xffffffff; 
#endif
		if(m_Count == 1)
		{
			EE_SAFEDELETEARRAY(m_pPairs); 
			m_Count = 0; 
			m_Capacity = 0; 
		}
		else
		{
			//Prevents allocations of negitive size memory
			if((m_Count - 1) < m_Capacity - STEP_SIZE && m_Capacity > STEP_SIZE)
			{
				m_Capacity -= STEP_SIZE; 
				Pair* pPairRealloc = EE_NEW Pair [m_Capacity]; 
				memcpy(&pPairRealloc[0], &m_pPairs[0], m_Capacity * sizeof(Pair)); 
				EE_SAFEDELETEARRAY(m_pPairs); 
				m_pPairs = pPairRealloc; 
			}

			const unsigned int uiShiftCount = m_Count - (keyIndex + 1); 
			if(uiShiftCount > 0)
			{
				const unsigned int uiShiftSize = uiShiftCount * sizeof(Pair); 
				Pair* pTemp = EE_NEW Pair [uiShiftCount]; 
				memcpy(pTemp, &m_pPairs[keyIndex + 1], uiShiftSize); 
				memcpy(&m_pPairs[keyIndex], pTemp, uiShiftSize); 
				EE_SAFEDELETEARRAY(pTemp); 

				EE_ZEROMEMORY(&m_pPairs[m_Count - 1], sizeof(Pair)); 
			}
			
			m_Count --; 
		}
	}
}

/**************************************
 *Returns the number of elements in a
 *list of the table key
 **************************************/
template<class T, class K>
unsigned int HashTable<T,K>::IndexElementCount(unsigned int idx) const
{ 
#ifdef _DEBUG
	if(idx < 0 || idx > m_Count - 1)
	{
		EE_LOGERROR("Hash table out of bound access"); 
		return NULL; 
	}
#endif

	return m_pPairs ? m_pPairs[idx].m_Count : 0;  
}

/**************************************
 *
 **************************************/
template<class T, class K>
K HashTable<T,K>::KeyAtTableIndex(unsigned int idx) const
{
#ifdef _DEBUG
	if(idx < 0 || idx > m_Count - 1)
	{
		EE_LOGERROR("Hash table out of bound access"); 
		return NULL; 
	}
#endif

	return m_pPairs[idx].m_Key; 
}

/**************************************
 *Returns the number of elements in a
 *list of the table key
 **************************************/
template<class T, class K>
unsigned int HashTable<T,K>::KeyElementCount(K key)
{ 
	Pair* pPair = NULL; 
	FindPair(&pPair, NULL,key); 
	return pPair ? pPair->m_Count : 0;  
}

/**************************************
 *Returns the number of keys in the 
 *table
 **************************************/
template<class T, class K>
unsigned int HashTable<T,K>::TableKeyCount(void) const
{ 
	return m_Count; 
}

/**************************************
 *Returns the number of keys in the 
 *table
 **************************************/
template<class T, class K>
unsigned int HashTable<T,K>::TableElementCount(void) const
{ 
#ifdef _DEBUG
	if((m_pPairs && !m_Count) || (!m_pPairs && m_Count))
	{
		EE_LOGERROR("Hashtable is inconsistant")
		return 0; 
	}
#endif

	int total = 0; 
	for(unsigned int i = 0;  i < m_Count;  i++)
	{
		Pair *pPair = &m_pPairs[i]; 
		
#ifdef _DEBUG
		if(!pPair || ((pPair->m_pData && !pPair->m_Count) || (!pPair->m_pData && pPair->m_Count)))
		{
			EE_LOGERROR("Hashtable key is inconsistant or invalid")
			continue; 
		}
#endif

		total += pPair->m_Count; 
	}
	return total; 
}

/**************************************
 *Returns a pointer to the beginning of
 *a tables keys data
 **************************************/
template<class T, class K>
T* HashTable<T,K>::Data(K key) 
{
	Pair* pPair = NULL; 
	FindPair(&pPair,NULL, key); 
	return pPair ? pPair->m_pData : NULL;  
}

/**************************************
 *Returns a pointer to the beginning of
 *the tables index
 **************************************/
template<class T, class K>
T* HashTable<T,K>::DataAtIndex(unsigned int idx) 
{
#ifdef _DEBUG
	if(idx < 0 || idx > m_Count - 1 || !m_pPairs)
	{
		EE_LOGERROR("Hash table out of bound access"); 
		return NULL; 
	}
#endif
	return m_pPairs ? m_pPairs[idx].m_pData : NULL; 
}

/**************************************
 *Indexing operator for data access
 **************************************/
template<class T, class K>
T* HashTable<T,K>::operator[] (unsigned int idx)
{
#ifdef _DEBUG
	if(idx > m_Count - 1)
	{
		EE_LOGERROR("Hash table out of bound access"); 
		return NULL; 
	}
#endif
	
	return m_pPairs[idx].m_pData; 
}

#endif HashTable__H__